package _11_binary_search_tree.exerc;

import _11_binary_search_tree.BSTree;
import org.junit.Test;

/**
 * @author: mornd
 * @dateTime: 2023/6/14 - 0:11
 * 查找二叉搜索树最近的公共祖先，（祖先也包括自己）
 * 前提：
 *      1、节点值唯一
 *      2、p 和 q 都存在
 *
 *              6
 *             /\
 *            2  8
 *          /\   /\
 *         0 4  7  9
 *          /\
 *         3  5
 *
 *  4和5的最近公共祖先是4
 *  4和8的最近公共祖先是6
 *
 *  结论：待查找节点 p q 在某一节点 r 的两侧，那么该节点就是最近的公共祖先
 */
public class LeetCodeTest2 {
    @Test
    public void test() {
        BSTree.BSTNode root = new BSTree.BSTNode(6);
        root.left = new BSTree.BSTNode(2);
        root.left.left = new BSTree.BSTNode(0);
        root.left.right = new BSTree.BSTNode(4);
        root.left.right.left = new BSTree.BSTNode(3);
        root.left.right.right = new BSTree.BSTNode(5);
        root.right = new BSTree.BSTNode(8);
        root.right.left = new BSTree.BSTNode(7);
        root.right.right = new BSTree.BSTNode(9);

        System.out.println(lowestCommonAncestor(root, 4, 5));
    }

    BSTree.BSTNode lowestCommonAncestor(
                            BSTree.BSTNode root, int p, int q) {
        BSTree.BSTNode curr = root;

        while (p < curr.key && q < curr.key || p > curr.key && q > curr.key) {
            if(p < curr.key) {
                curr = curr.left;
            } else {
                curr = curr.right;
            }
        }
        return curr;
    }
}
